In this paper, we consider solving multiple-block separable convexminimization problems using alternating direction method of multipliers (ADMM).Motivated by the fact that the existing convergence theory for ADMM is mostlylimited to the two-block case, we analyze in this paper, both theoretically andnumerically, a new strategy that first transforms a multi-block problem into anequivalent two-block problem (either in the primal domain or in the dualdomain) and then solves it using the standard two-block ADMM. In particular, wederive convergence results for this two-block ADMM approach to solvemulti-block separable convex minimization problems, including an improvedO(1/\epsilon) iteration complexity result. Moreover, we compare the numericalefficiency of this approach with the standard multi-block ADMM on severalseparable convex minimization problems which include basis pursuit, robustprincipal component analysis and latent variable Gaussian graphical modelselection. The numerical results show that the multiple-block ADMM, althoughlacks theoretical convergence guarantees, typically outperforms two-blockADMMs.
展开▼
